Optimality of Fast Matching Algorithms for Random Networks with Applications to Structural Controllability

摘要

Network control refers to a very large and diverse set of problems includingcontrollability of linear time-invariant dynamical systems, where the objectiveis to select an appropriate input to steer the network to a desired state.There are many notions of controllability, one of them being structuralcontrollability, which is intimately connected to finding maximum matchings onthe underlying network topology. In this work, we study fast, scalablealgorithms for finding maximum matchings for a large class of random networks.First, we illustrate that degree distribution random networks are realisticmodels for real networks in terms of structural controllability. Subsequently,we analyze a popular, fast and practical heuristic due to Karp and Sipser aswell as a simplification of it. For both heuristics, we establish asymptoticoptimality and provide results concerning the asymptotic size of maximummatchings for an extensive class of random networks.